1. Field of the Invention
This invention generally relates to concurrency control in a multi-user data processing environment and, more particularly, to a new concurrency control (CC) method which restricts the wait depth of waiting transactions to a predetermined depth and takes into account the progress made by transactions in conflict resolution. In a preferred embodiment of the invention as applied to a centralized environment, the wait depth may be limited to one. The invention is generalized to a distributed environment by adopting a time based wait function.
2. Description of the Prior Art
In a multi user data processing environment, some sort of concurrency control is needed in order to avoid problems when two or more users attempt to update a field of a record in the database on the basis of an initial value of that field. One approach to concurrency control is known as locking. Another is known as time-stamping or optimistic concurrency control. Of the two, locking is the more important as it is the method that is predominantly used.
A transaction can obtain a lock on a record by issuing a request to a system component called the lock manager. If a transaction holds an exclusive lock on some object, say, a database record, then no other transaction can acquire a lock of any type on that object until the first transaction releases its lock. Any transaction that intends to update a record must first acquire a lock on it. If a lock cannot be acquired, the transaction is blocked and goes into a wait state. The transaction is restarted when the record becomes available and the lock can be granted. While this locking protocol solves the lost update problem, it introduces two others. One is the problem of deadlock, in which two or more transactions are in a simultaneous wait state, each waiting for the others to release a lock required for it to proceed. The other problem, which can be encountered in high performance applications (where typically a substantial number of transactions are being processed concurrently) is that many or even most of these transactions can be waiting at a given time, even without the presence of deadlock. Increasing the level of concurrency (the number of transactions attempting to proceed simultaneously) can actually reduce the number doing useful work (i.e., not waiting or in deadlock) at a given time.
The problem of deadlock has been extensively studied. In general, the lock manager must be capable of detecting the occurrence of deadlocks and resolve them. Resolving the deadlock amounts to choosing one of the locked transactions and rolling it back. This process involves terminating the transaction and undoing all its updates and releasing its locks so that the resources concerned can be allocated to other transactions.
The general problems associated with concurrency in database transactions is considered in more detail by C. J. Date at Chapter 3, "Concurrency", An Introduction to Database Systems, Vol. II, Addison-Wesley Publishing Company (1983). The reader is referred to that text for more information on the various concurrency problems and protocols used, especially in the locking type concurrency controls.
A running priority (RP) concurrency control (CC) is described in an article entitled "Limitations of Concurrency in Transaction Processing" by P. A. Franaszek and J. T. Robinson, published in ACM Transactions on Database Systems 10, March 1985, pp. 1 to 28. This method results in improved performance compared to standard locking because it approximates "essential blocking" by having no transaction blocked (i.e., waiting for a lock) held by another blocked transaction.
A problem with the RP method, as well as others including optimistic CC, is the quadratic effect; i.e., "long" transactions accessing a large number of data items are affected adversely by lock contention in a "quadratic" manner. More specifically, the more locks a transaction holds, the more susceptible it is to lock conflicts, and the time spent by the transaction in the system increases proportionally to the number of locks held, making the transaction more susceptible to lock conflicts and restarts.
The problem of concurrency control in the general case of a distributed transaction processing system becomes even greater due to the increasing disparity between processor speeds and data access latencies and the large number of processors typical of such systems. In distributed systems, each transaction executes as a number of communicating subtransactions running concurrently at different nodes in the system. Each subtransaction accesses data items stored at the node at which it runs. An overview of such systems and known distributed concurrency control methods can be found, for example, in Chapter 12 of Korth and Silberschatz, Database System Concepts, McGraw-Hill (1986).
The most commonly used approach to distributed concurrency control is to use the standard centralized locking method at each node for all subtransactions running at that node. Each subtransaction of a given transaction holds all locks it acquires until all subtransactions signal completion, after which a commit protocol is followed for recovery purposes. All locks are then released by each subtransaction as part of the completion of the commit protocol. Distributed deadlock detection is a known problem under this approach, and a variety of techniques are known to deal with it. A more serious problem is that the level of data contention is likely to be significantly higher than that of a centralized system with similar total processing power and with a similar transaction processing workload, for the following reasons. First, compared to the centralized system, there are additional delays for each transaction due to communication among subtransactions during execution and during the commit phase, resulting in increased lock holding times. Second, the total number of processors in the distributed system could be significantly larger than in the centralized case, thus requiring a higher total level of concurrency just to utilize the processors.
The trend towards longer and more complex transactions supported by distributed systems substantially increases the amount of data contention, which could limit the total available throughput. It is known that the usual locking methods of concurrency control are not well suited to environments where data contention is a significant factor.